
#include<vector>
using namespace std;
/**
 * 递归实现折半查找
 * O(log2_n)
 * O(log2_n)
 * @param arr 线性表
 * @param k 关键字
 * @param left 从1开始
 * @param right arr.size()-1
 * @return 关键字k的下标
 */
int binary_search(vector<int> arr,int k,int left,int right){
    if(left>right)return 0;
    int mid=(left+right)/2;
    if(k>arr[mid])
        binary_search(arr,k,mid+1,right);
    else if(k<arr[mid])
        binary_search(arr,k,left,mid-1);
    else
        return mid;
}